import java.util.Stack;

public class code02 {

//    链表相加
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // 这到题可以将链表的值存储到栈中进行计算，之后将计算的值进行重新构建即可
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        // 首先进行一下特殊情况判断
        if (head1 == null || head1.val == 0) {
            return head2;
        }
        if (head2 == null || head2.val == 0) {
            return head1;
        }

        ListNode f1 = head1;
        ListNode f2 = head2;
        while (f1 != null) {
            s1.push(f1.val);
            f1 = f1.next;
        }
        while (f2 != null) {
            s2.push(f2.val);
            f2 = f2.next;
        }

        // 之后再加减操作上，需要考虑一个进位问题，所以先设置一个标记
        int flag = 0;
        // 创建出两个新的节点用来组成新的链表
        ListNode newList = null;
        ListNode Head = null;

        // 通过 while 循环来实现相加将两个链表组合
        while (!s1.isEmpty() || !s2.isEmpty() || flag != 0) {
            int a = 0;
            int b = 0;
            // 进行两个栈的元素出栈判断
            if (s1.isEmpty()) {
                a = 0;
            } else {
                a = s1.pop();
            }
            if (s2.isEmpty()) {
                b = 0;
            } else {
                b = s2.pop();
            }

            // 将两数进行相加 操作
            int c = a + b + flag;
            // 这里获取到两数相加后的进位数
            flag = c / 10;

            // 之后实现组建新链表
            newList = new ListNode(c % 10);
            newList.next = Head;
            Head = newList;
        }
        return Head;
    }
}
